#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> PII; // 用pair --> 距离+编号

const int N = 1e5 + 5e4 + 10;

int n, m;
int h[N], e[N], w[N], ne[N], idx;
int dist[N];
bool st[N];

void add(int a, int b, int c) {
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int dijkstra() {
	memset(dist, 0x3f, sizeof dist); // 初始化距离为正无穷
	dist[1] = 0; // 将第一个点到自己的距离初始化为0
	priority_queue<PII, vector<PII>, greater<PII>> heap; // 用小根堆（pair --> 距离+编号）
	heap.push({0, 1}); // 将第一个点入堆
	
	while (heap.size()) { // 遍历堆
		auto t = heap.top(); // 取出堆顶元素(即距离集合最近的不在集合内的)
		heap.pop(); // 取出后将堆顶弹出
		
		int distance = t.first, num = t.second; // 分别取出堆顶的first-->距离,second-->编号
		if (st[num]) continue; // 如果该点已经被确定过则继续找点
		
		st[num] = true; // 将取出来的编号标记为已被确定过
		for (int i = h[num]; i != -1; i = ne[i]) { // 以取出来的点来更新与之联通的其他所有点
			int j = e[i]; // 取出与该点联通的点的编号
			if (dist[j] > dist[num] + w[i]) { // 如果用该点能使该联通点的距离更短
				dist[j] = dist[num] + w[i];  // 则将该联通点的距离更新
				heap.push({dist[j], j}); // 且将该点入堆
			}
		}
	}
	
	if (dist[n] == 0x3f3f3f3f) return -1; // 如果第n个点到起点的距离为正无穷则说明无法从起点走到第n个点，则说明没有该最短路-->返回-1
	return dist[n]; // 如果有最短路，返回第n个点的到起点的距离
} 

int main() {
	scanf("%d%d", &n, &m);
	
	memset (h, -1, sizeof h); // 初始化表头为-1
	while (m -- ) { // 读入边
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		add(a, b, c);
	}
	
	printf("%d\n", dijkstra()); // 输出答案
	 
	return 0; // 结束快乐
}